package com.desheng.bigdata.ds.stack;

/**
 * @Description 基于栈的括号匹配问题
 * @Author deshenglijun
 * @Date 2020/5/15 20:50
 * @Version 1.0
 *
 * 给定一个字符串，里面可能包含"()"小括号和其他字符
 * 例如
 *  "(上海)(长安)"： 匹配正确
 *  "上海((长安))"： 匹配正确
 *  "上海(长安(北京)(深圳)南京)"： 匹配正确
 *  "上海((长安)"： 匹配错误
 *  "(上海))长安"： 匹配错误
 */
public class BracketsMatch {
    public static void main(String[] args) {
        String str = "上海((长安)";
        boolean match = isMatch(str);
        System.out.println(str + "中得括号是否匹配：" + match);
    }

    private static boolean isMatch(String str) {
        if(str == null || str.equalsIgnoreCase("")) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for(char ch : str.toCharArray()) {
            if(ch == '(') {
                stack.push(ch);
            } else if (ch == ')') {
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}
